CS229：13-SVM（四）非线性决策边界

当数据中存在异常点时，比如上述的情况，导致原先可以用直线 a 分割的数据现在不得不用 b 来进行，以保证完美的分割。由此我们引出了非线性决策边界（_non-linear decision boundaries_）来解决这样的问题。

观察原 SVM 问题的目标：

$$\min_{w, b} \frac{1}{2}||w|^2 \\\ \text{ s.t. }y^{(i)} \cdot (w^T \cdot x^{(i)}+b) \geq 1, i=1,\ldots,m$$

我们为原公式增加惩罚项，对不同的数据点增加不同的惩罚，使得所有样本能够更好地分割：

$$\min_{w, b} \frac{1}{2}||w|^2+c\sum_{i=1}^m\xi_i, \xi_i\geq0$$

使得

$$y^{(i)} \cdot (w^T \cdot x^{(i)}+b) \geq 1-\xi_i, i=1,\ldots,m$$

注意到，我们之前认为$ y^{(i)} \cdot (w^T \cdot x^{(i)}+b) \geq 1 $是分类正确的，在这里我们允许一部分样本小于 1，也就是说明我们允许了一部分样本分类错误。

构建拉格朗日算子：

$${\cal L}(w, b, \xi, \alpha, \gamma) = \frac{1}{2}||w|^2+c\sum_i\xi_i-\sum_i^m\alpha_i(y^{(i)} (w^T \cdot x^{(i)}+b)-1+\xi_i)-\sum_i^m\gamma_i\xi_i$$

对偶：

$$\max W(\alpha) = \sum_{i=1}\alpha_i-\frac{1}{2}\sum_{i=1}\sum_{j=1}\alpha_i\alpha_jy_iy_j\langle x_i \cdot x_j \rangle$$

跟原先的 SVM 问题的唯一区别在于其限制条件为：

$$\sum_{i=1}^my^{(i)}\alpha_i=0 \\\ 0 \leq \alpha_i \leq c$$

其收敛条件：

• 对于大部分数据点：

  $$\alpha_i=0 \Rightarrow y^{(i)} (w^T \cdot x^{(i)}+b) \geq 1$$

• 对于异常点：

  $$\alpha_i = c$$

• 对于最近点：

  $$0<\alpha_i<c$$

坐标上升法（Coordinate Ascent）

考虑优化问题：

$$\max W(\alpha_1, \alpha_2, ..., \alpha_m)$$

不考虑约束条件，

重复 {

​ For i = 1 to m:

$$\alpha_i := \arg \max_{\hat{\alpha}_i} W(\alpha_1,\ldots,{\hat{\alpha}}_i,\ldots,\alpha_m)$$

} 直到收敛；

这个算法，可以认为是执行了以下这个过程（以 m=2 为例）：

顺序最小优化算法（Sequential minimal optimization, SMO）

顺序最小优化算法的基本理念就是在坐标上升法的基础上，改成一次性优化其中两个$\alpha$，而固定其他的$m-2$个$\alpha$。

假如我们更新$\alpha_1, \alpha_2$：

因为在之前我们提到:

$$\sum_i^m \alpha_iy^{(i)}=0$$

于是有：

$$\alpha_1 y^{(1)}+\alpha_2 y^{(2)} = -\sum_{i=3}^m\alpha_iy^{(i)}= \zeta$$

那么

$$\alpha_1=\frac{\zeta-\alpha_2y^{(2)}}{y^{(1)}}$$ $$W(\alpha_1, \alpha_2, ..., \alpha_m) = W(\frac{\zeta-\alpha_2y^{(2)}}{y^{(1)}}, \alpha_2, ..., \alpha_m)$$

在非线性决策边界优化问题中，其实$W$是一个关于$\alpha_i$的二次函数，固定其他$\alpha$之后，$W$函数就可以被简化为：

$$a\alpha_2^2+b \alpha_2 + c$$

很容易就能求解。